package leetcode;

/**
 * Created by Ghost on 2015/2/4 0004.
 */
public class Next_Permutation {
    private void reverse(int[] num, int start, int end) {
        while (start < end) {
            int i = num[start];
            num[start] = num[end];
            num[end] = i;
            start++;
            end--;
        }
    }

    public void nextPermutation(int[] num) {
        if (num == null || num.length == 0)
            return;
        int maxI = -1, maxL = -1;
        for (int i = 0; i < num.length - 1; i++) {
            if (num[i] < num[i + 1]) {
                maxI = i + 1;
            }
        }
        if (maxI == -1) {
            reverse(num, 0, num.length - 1);
        } else {
            for (int l = maxI; l < num.length; l++) {
                if (num[l] > num[maxI - 1]) {
                    maxL = l;
                }
            }
            int i = num[maxI - 1];
            num[maxI - 1] = num[maxL];
            num[maxL] = i;
            reverse(num, maxI, num.length - 1);
        }
    }
}
